﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>

//直接插⼊排序
//当插⼊第 i(i >= 1) 个元素时，前⾯的 array[0], array[1], …, array[i - 1] 已经排好序，此时
//⽤ array[i] 的排序码与 array[i - 1], array[i - 2], … 的排序码顺序进⾏⽐较，找到插⼊位置
//即将 array[i] 插⼊，原来位置上的元素顺序后移


void InsertionSort(int* a ,int n)
{
   /*
        for (int i = 0; i < n - 1; i++)
        {
            int end = i;
            int tmp = a[end + 1];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + 1] = a[end];
                    end--;
                }
                else
                {
                    break;
                }
            }
            a[end + 1] = tmp;*/
   
    for (int  i = 0; i < n - 1; i++)
    {
        int end = i;
        int temp = a[end + 1];
        while (end >= 0 && a[end] > temp)
        {
            a[end + 1] = a[end];
            end--;
        }
        a[end + 1] = temp;
    }
     



}

 // 插入排序

//void insertionSort(vector<int>& arr) {
//    int n = arr.size();
//    for (int i = 1; i < n; i++) {
//        int key = arr[i];
//        int j = i - 1;
//
//        // 将大于key的元素向后移动
//        while (j >= 0 && arr[j] > key) {
//            arr[j + 1] = arr[j];
//            j--;
//        }
//        arr[j + 1] = key;
//    }
//}

int main()
{
    int array[8] = {2,6,4,7,8,5,3,1};
    int num = 8;
    InsertionSort( array, num);
    for (int  i = 0; i < num; i++)
    {
        printf("%d ", array[i]);
    }
     return 0;
}